package sort.advance;

import java.util.Arrays;

/**
 * 快速排序
 * @author caasi
 * @since 2022-01-07 11:15:06
 */
public class QuickSort {

    public static void main(String[] args) {
        int n = 50000000;
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            int r = (int) (Math.random() * 1000);
            arr[i] = r;
        }
        //int arr[] = new int[]{56,74,34,24,89,112,34,21,12,9};
        //System.out.println(Arrays.toString(arr));
        long start = System.currentTimeMillis();
        QuickSort.sort(arr);
        long end = System.currentTimeMillis();
        System.out.println("耗时：" + (end - start) + "ms");//6066ms
        //System.out.println(Arrays.toString(arr));
    }

    public static void sort(int[] arr) {
        int low = 0;
        int high = arr.length - 1;
        sort(arr, low, high);
    }

    private static void sort(int[] arr, int low, int high) {
        //递归退出条件
        if (low >= high) {
            return;
        }
        //排序并且找出分界值并返回其下标
        //分界值左边的值都小于分界值，分界值右边的值都大于分界值
        int partition = partition(arr, low, high);
        //递归排序分界值左右两边的两组数据
        sort(arr, low, partition - 1);
        sort(arr, partition + 1, high);
    }

    private static int partition(int[] arr, int low, int high) {
        //每次都选择小组内的第一个元素为分界值
        int key = arr[low];
        //设置两个指针 一个从小组的最左边开始 另一个从小组的最后一个元素 + 1 的位置开始
        int left = low;
        int right = high + 1;

        //进行排序
        while (true) {
            //首先移动右指针，如果右指针的元素小于分界值或已经到达最左边，停止移动右指针
            while (key < arr[--right]) {
                if (right == low) {
                    break;
                }
            }
            //再移动左指针，如果左指针的元素大于分界值或已经到达最右边，停止移动指针
            while (key > arr[++left]) {
                if (left == high) {
                    break;
                }
            }
            //循环的退出条件是左指针大于等于右指针，否则交换左右两个指针的位置
            if (left >= right) {
                break;
            } else {
                int temp = arr[left];
                arr[left] = arr[right];
                arr[right] = temp;
            }
        }

        //结束之后交换right指针和key的位置
        int temp = arr[low];
        arr[low] = arr[right];
        arr[right] = temp;

        //一定要返回右指针下标
        return right;
    }
    
}
